from collections import deque
from typing import List


class Solution:
    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:
        # n为高度,m为宽度
        n, m = len(terrain), len(terrain[0])

        # 最快速度永远不会超过(当前高度+1)
        now_height = terrain[position[0]][position[1]] + 1

        # 访问状态：[当前x,当前y,当前速度]
        visited = [[[False] * (now_height + 1) for _ in range(m)] for _ in range(n)]
        visited[position[0]][position[1]][1] = True

        ans = []

        # 状态：[当前x,当前y,当前速度] (当前点的减速值已经被记录)
        queue = deque([[position[0], position[1], 1]])
        while queue:
            x1, y1, s1 = queue.popleft()
            h1 = terrain[x1][y1]
            for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]:
                if not 0 <= x2 < n or not 0 <= y2 < m:
                    continue
                o2 = obstacle[x2][y2]
                h2 = terrain[x2][y2]
                s2 = s1 + h1 - h2 - o2
                if s2 > 0 and visited[x2][y2][s2] is False:
                    if s2 == 1:
                        ans.append([x2, y2])
                    visited[x2][y2][s2] = True
                    queue.append([x2, y2, s2])
                # print(x2, y2, o2, h1, h2, ",", s1, "->", s2)
            # print(queue)

        ans.sort()

        return ans


if __name__ == "__main__":
    # [[0,1],[1,0],[1,1]]
    print(Solution().bicycleYard(position=[0, 0],
                                 terrain=[[0, 0],
                                          [0, 0]],
                                 obstacle=[[0, 0],
                                           [0, 0]]))

    # [[0,1]]
    print(Solution().bicycleYard(position=[1, 1],
                                 terrain=[[5, 0],
                                          [0, 6]],
                                 obstacle=[[0, 6],
                                           [7, 0]]))
